package Day2025_03_01;

import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class LeetCode23 {
    public ListNode mergeKLists2(ListNode[] lists) {
        // 小根堆
        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;
        for (ListNode list : lists) if (list != null) pq.offer(list);
        while (!pq.isEmpty()) {
            ListNode cur = pq.poll();
            prev.next = cur;
            prev = cur;
            if (cur.next != null) pq.offer(cur.next);
        }
        return newHead.next;
    }

    public ListNode mergeKLists(ListNode[] lists) {
        return mergeSort(lists, 0, lists.length - 1);
    }
    private ListNode mergeSort (ListNode[] lists, int left, int right) {
        if (left > right) return null;
        if (left == right) return lists[left];
        int mid = (left + right) / 2;
        ListNode l1 = mergeSort(lists, left , mid);
        ListNode l2 = mergeSort(lists, mid + 1, right);
        return merge(l1, l2);
    }
    private ListNode merge (ListNode l1, ListNode l2) {
        ListNode cur1 = l1, cur2 = l2;
        ListNode newHead = new ListNode(0);
        ListNode prev = newHead;
        // 合併l1, l2
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                prev.next = cur1;
                prev = cur1;
                cur1 = cur1.next;
            } else {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
        if (cur1 == null) prev.next = cur2;
        if (cur2 == null) prev.next = cur1;
        return newHead.next;
    }
}
